/*
 * BSharpTreeIndex.hpp
 *
 *  Created on: Sep 29, 2010
 *      Author: nicoabie
 */

#ifndef BSHARPTREEINDEX_HPP_
#define BSHARPTREEINDEX_HPP_

template<class Key, class DataRef, class Compare = std::less<Key>,
		class IndexPageContainer = IndexPage<Key, DataRef, Compare> ,
		class LeafPageContainer = LeafPage<Key, DataRef, Compare>>
class BSharpTreeIndex
{
public:
	typedef Key key_type;
	typedef Compare compare_type;
	typedef Page<Key,DataRef,Compare> page;
	typedef IndexPage<Key,DataRef,Compare> indexPage;
	typedef LeafPage<Key,DataRef,Compare> leafPage;
	typedef page::PagePtr_t PagePtr_t;
	typedef page::iPagePtr_t iPagePtr_t;
	typedef page::lPagePtr_t lPagePtr_t;
	typedef leafPage::value_type value_type;
	typedef value_type* pointer;
	typedef value_type& reference;
	typedef size_t size_type;
	typedef ptrdiff_t difference_type;

protected:
	PagePtr_t root;

public:
	BSharpTreeIndex(PagePtr_t p):root(p){};
	BSharpTreeIndex();
	BSharpTreeIndex(BSharpTreeIndex& x);
	template<class InputIterator>
	BSharpTreeIndex(InputIterator f,InputIterator l);
	virtual ~BSharpTreeIndex();
	class iterator::public
std::iterator<std::random_access_iterator_tag,value_type,difference_type>;
	iterator begin();
	iterator end();
	size_type size();
	iterator find(const key_type& k);
	iterator lower_bound(const key_type& k);
	iterator upper_bound(const key_type& k);
	std::pair<iterator,iterator> equal_range(const key_type& k);
	iterator insert(const value_type& aPair);
	template<class InputIterator>
	void insert(InputIterator f, InputIterator l);
	void erase(iterator pos);
	void erase(iterator f, iterator l);
	size_type erase(const key_type& k);
	size_type max_size();
	void clear();

private:
	lPagePtr_t chooseLeaf(const key_type& k);
	void adjustTree(const key_type& k, PagePtr_t page);
	void condenseTree(PagePtr_t page);
	void updateKey(PagePtr_t p, const key_type& k);
};

#endif /* BSHARPTREEINDEX_HPP_ */
